//========================================================================
/**
*  Copyright (c), 2007-2009.
*  @file	cx_list.h
*  @author	godwinguo
*  @email	godwinguo@tencent.com
*  @brief	Red-black search tree
*  @version	1.0.0
*  @history
*    <author>      <time>      <version>     <desc>
*  ------------ ------------  ------------  -----------------
*    godwinguo   2010/01/19     1.0.0        Copy from BaseStruct
*/
//========================================================================

#include "cx_hashtab.h"
#include "cx_memory.h"
#include "cx_debug.h"

/*************************************************************************
* MACRO
*************************************************************************/

#ifndef NULL
#define NULL	(0)
#endif	// #ifndef NULL

/*************************************************************************
* LOCAL FUNCTION
*************************************************************************/

static signed long		cmpatom(const void *x, const void *y);
static unsigned long	hashatom(const void *key);

/*************************************************************************
* IMPLEMENTATION
*************************************************************************/

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
static signed long cmpatom(const void *x, const void *y) {
	return (signed long)(x != y);
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
static unsigned long hashatom(const void *key) {
	return (unsigned long)key>>2;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
hash_table_ptr_t cx_ht_New( unsigned long hint,
		signed long cmp(const void *x, const void *y),
		unsigned long hash(const void *key) )
{
	hash_table_ptr_t table;
	int i;
	static unsigned long primes[] = { 509, 509, 1021, 2053, 4093,
		8191, 16381, 32771, 65521, 0xFFFFFFFF };
	ASSERT(hint >= 0);
	for (i = 1; primes[i] < hint; i++)
		;
	table = cx_malloc(sizeof (*table) + primes[i-1]*sizeof (table->buckets[0]));
	table->size = primes[i-1];
	table->cmp  = cmp  ?  cmp : cmpatom;
	table->hash = hash ? hash : hashatom;
	table->buckets = (struct binding **)(table + 1);
	for (i = 0; i < table->size; i++)
		table->buckets[i] = NULL;
	table->length = 0;
	table->timestamp = 0;
	return table;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
void *cx_ht_get(hash_table_ptr_t table, const void *key) 
{
	int i;
	struct binding *p;
	ASSERT(table);
	ASSERT(key);
	i = (*table->hash)(key)%table->size;
	for (p = table->buckets[i]; p; p = p->link)
		if ((*table->cmp)(key, p->key) == 0)
			break;
	return p ? p->value : NULL;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
void *cx_ht_put(hash_table_ptr_t table, const void *key, void *value) 
{
	int i;
	struct binding *p;
	void *prev;
	ASSERT(table);
	ASSERT(key);
	i = (*table->hash)(key)%table->size;
	for (p = table->buckets[i]; p; p = p->link)
		if ((*table->cmp)(key, p->key) == 0)
			break;
	if (p == NULL) {
		// #define NEW(p) ((p) = ALLOC((long)sizeof *(p)))
		//NEW(p);
		p = cx_malloc( sizeof( *p ) );
		p->key = key;
		p->link = table->buckets[i];
		table->buckets[i] = p;
		table->length++;
		prev = NULL;
	} else
		prev = p->value;
	p->value = value;
	table->timestamp++;
	return prev;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
unsigned long cx_ht_length(hash_table_ptr_t table) 
{
	if ( NULL == table )
		return 0;
	
	return table->length;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
void cx_ht_map(hash_table_ptr_t table,
	void apply(const void *key, void **value, void *cl),
	void *cl)
{
	int i;
	unsigned stamp;
	struct binding *p;
	ASSERT(table);
	ASSERT(apply);
	stamp = table->timestamp;
	for (i = 0; i < table->size; i++)
		for (p = table->buckets[i]; p; p = p->link) {
			apply(p->key, &p->value, cl);
			ASSERT(table->timestamp == stamp);
		}
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
void *cx_ht_remove(hash_table_ptr_t table, const void *key) 
{
	int i;
	struct binding **pp;
	ASSERT(table);
	ASSERT(key);
	table->timestamp++;
	i = (*table->hash)(key)%table->size;
	for (pp = &table->buckets[i]; *pp; pp = &(*pp)->link)
		if ((*table->cmp)(key, (*pp)->key) == 0) {
			struct binding *p = *pp;
			void *value = p->value;
			*pp = p->link;
			cx_free(p);
			table->length--;
			return value;
		}
	return NULL;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
void **cx_ht_toArray(hash_table_ptr_t table, void *end)
 {
	int i, j = 0;
	void **array;
	struct binding *p;
	ASSERT(table);
	array = cx_malloc((2*table->length + 1)*sizeof (*array));
	for (i = 0; i < table->size; i++)
		for (p = table->buckets[i]; p; p = p->link) {
			array[j++] = (void *)p->key;
			array[j++] = p->value;
		}
	array[j] = end;
	return array;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
void cx_ht_Release(hash_table_ptr_t table) 
{
	ASSERT(table );// && *table);
	if ((table)->length > 0) {
		int i;
		struct binding *p, *q;
		for (i = 0; i < (table)->size; i++)
			for (p = (table)->buckets[i]; p; p = q) {
				q = p->link;
				cx_free(p);
			}
	}
	cx_free(table);
}
